1. Field of the Invention
The present invention relates to an integrated circuit having a multiplier that provides signed and/or unsigned overflow flags.
2. Description of the Prior Art
Although integer multiplication is a ubiquitous arithmetic operation, implementing it on a microprocessor requires a large amount of resources and/or takes many clock cycles to complete, and hence different implementations of the multiply instruction are found on commercial microprocessors. While some microprocessors support only a "multiply step" instruction, some high-end processors implement a multiplier in hardware. Many processors achieve multiplication using the Booth algorithm.
In most microprocessors, the possibility of overflow exists when performing multiplication, as follows: If two n-bit operands are multiplied, the result is 2n-bits wide in a general case. Since the ALU is typically n-bits wide, it is impractical to compute the full 2n-bit result of a multiplication using the existing ALU. Consequently, many processors compute only the lower n-bits of the result; thus, there may be loss of precision. That is, the result is correct, and there is no loss of precision, only if the upper n bits are zero. Otherwise, to obtain full precision in a n-bit multiplier, the full product has to be computed by decomposing the multiplicand and the multiplier each into n/2 bit operands and carrying out four multiplications, and then reconstructing the complete 2n-bit product. Thus, for the processors which compute the lower n-bits of the result, there has to be a mechanism, such as setting a flag in the status word, to signal whether there is a loss of precision.
For example, the product obtained by multiplying two 32 bit numbers is a 64 bit number. However, if the product is computed to only 32 bits, as is typical in single-chip microprocessors, then the programmer must ensure by various software techniques that the result does not exceed 32 significant bits. Otherwise, the most significant bits of the result could be lost. Another way to avoid overflow is to utilize double-precision multiplication (e.g., 64 bits). However, that requires either a significant increase in hardware requirements, or else an increase in computation time. It is known to include one or more overflow flags in the circuitry of integrated circuit multipliers. The overflow ("V") flag is set when an overflow results from the multiplication of signed numbers. The carry ("C") flag is set when an overflow results from the multiplication of unsigned numbers. However, in many prior art applications, the control of the "V" flag has required double-precision multiplication, thereby increasing the computation time, or requiring significant additional circuitry, as compared to the case where only single-precision multiplication is required.
Multiplication of two operands that are represented in 2's complement form is complicated by the fact that the upper word (n bits) of the result is different depending upon whether the two operands are to be treated as signed or unsigned (note that the lower n bits of the result are always the same). That is, the most significant bit of a signed number is the sign bit, with a "0" representing a positive number and a "1" representing a negative number. For an unsigned number, the first bit is simply the most significant digit. Hence, for example, for word size n=8, a signed multiplication of 0xff (where 0x represents hexadecimal representation) with itself yields 0x01 as the lower product and 0x00 as the upper product. On the other hand, an unsigned multiplication of 0xff with itself again yields 0x01 as the lower product but 0xfe as upper product. Furthermore, there are cases where the upper word is zero but the lower n bits do not correctly represent the product. For example, multiplying two positive integers such as 0x40 by 0x20 gives 0x80 as a result, which is negative in 2's complement representation. Some microprocessors thus support separate signed and unsigned multiply instructions, and each instruction sets the same flag (usually the "C" flag) to signal a loss of precision.
In one commercial 32-bit microprocessor that uses the shift-and-add technique to perform multiplication, all multiplications are done on unsigned operands. If multiplication is to be performed on signed operands, they are first converted to unsigned form, the multiplication is accomplished, and the result converted back to signed number form. A single flag (V) is then set if overflow occurs during multiplication, although the control of the flag may be different for the two cases. However, for increased speed of operation, most microprocessors accomplish multiplication with the modified Booth algorithm, which repeatedly uses the arithmetic-logic unit (ALU). It has proven especially difficult for workers in the art to implement an overflow indicator that would reliably indicate overflow in essentially real-time when using the Booth algorithm; that is, while the multiplication is in progress, so that the value of the C and V flags are available when the multiplication is complete. This can be understood when it is realized that there are 2.sup.64 possible cases under which the flags could be tested for 32 bit multiplication. It appears that no microprocessors that implement an overflow indicator for use with a Booth multiplier have been developed.